package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.Graph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.weight.WeightedPath
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.algorithms.shortestpath.internal.ShortestDistances
import org.apache.commons.graph.collections.FibonacciHeap
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 *
 * @param <V> the Graph vertices type.
 * @param <WE> the Graph weighted edges type
 * @param <W> the weight type
</W></WE></V> */
interface ShortestPathAlgorithmSelector<V, WE, W> {
    /**
     * Calculates the shortest path using the A* algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the class responsible for operations on weights
     * @return
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingAStar(weightOperations: WO): HeuristicBuilder<V, WE, W>

    /**
     * Calculates the shortest path using bidirectional Dijkstra's algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the class responsible for operations on weights
     * @return a path which describes the shortest path, if any, otherwise a [PathNotFoundException] will be thrown
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingBidirectionalDijkstra(weightOperations: WO): WeightedPath<V, WE, W>

    /**
     * Calculates the shortest path using Dijkstra's algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the class responsible for operations on weights
     * @return a path which describes the shortest path, if any, otherwise a [PathNotFoundException] will be thrown
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingDijkstra(weightOperations: WO): WeightedPath<V, WE, W>
}



/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

internal class DefaultShortestPathAlgorithmSelector<V, WE, W>(
    private val graph: Graph<V, WE>,
    private val weightedEdges: Mapper<WE, W>,
    private val source: V,
    private val target: V
) : ShortestPathAlgorithmSelector<V, WE, W> {
    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingAStar(weightOperations: WO): HeuristicBuilder<V, WE, W> {
        //var weightOperations = weightOperations
        //weightOperations = Assertions.checkNotNull(weightOperations, "A* algorithm can not be applied using null weight operations")
        return DefaultHeuristicBuilder(graph, weightedEdges, source, target, weightOperations)
    }

    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingBidirectionalDijkstra(weightOperations: WO): WeightedPath<V, WE, W> {
        //var weightOperations = weightOperations
        //weightOperations = Assertions.checkNotNull(
        //    weightOperations,
        //    "Bidirectional Dijkstra algorithm can not be applied using null weight operations"
        //)

        val shortestDistancesForward = ShortestDistances<V, W>(weightOperations)
        shortestDistancesForward.setWeight(source, weightOperations.identity())

        val shortestDistancesBackwards = ShortestDistances<V, W>(weightOperations)
        shortestDistancesBackwards.setWeight(target, weightOperations.identity())

        val openForward = FibonacciHeap(shortestDistancesForward)
        openForward.add(source)

        val openBackwards = FibonacciHeap(shortestDistancesBackwards)
        openBackwards.add(target)

        val closedForward: MutableSet<V> = HashSet()

        val closedBackwards: MutableSet<V> = HashSet()

        val predecessorsForward = org.apache.commons.graph.algorithms.shortestpath.PredecessorsList(
            graph,
            weightOperations,
            weightedEdges
        )

        val predecessorsBackwards =
            org.apache.commons.graph.algorithms.shortestpath.PredecessorsList(
                graph,
                weightOperations,
                weightedEdges
            )

        var best: W? = null
        var touch: V? = null

        while (!openForward.isEmpty() && !openBackwards.isEmpty()) {
            if (best != null) {
                val tmp = weightOperations.append(
                    shortestDistancesForward.getWeight(openForward.peek()!!)!!,
                    shortestDistancesBackwards.getWeight(openBackwards.peek()!!)!!
                )

                if (weightOperations.compare(tmp, best) >= 0) {
                    return predecessorsForward.buildPath(source, touch!!, target, predecessorsBackwards)
                }
            }

            var vertex = openForward.removeAndGet()!!

            closedForward.add(vertex)

            for (v in graph.getConnectedVertices(vertex)) {
                if (!closedForward.contains(v)) {
                    val edge = graph.getEdge(vertex, v)!!
                    if (shortestDistancesForward.alreadyVisited(vertex)) {
                        val shortDist = weightOperations.append(shortestDistancesForward.getWeight(vertex)!!, weightedEdges.map(edge))

                        if (!shortestDistancesForward.alreadyVisited(v)
                            || weightOperations.compare(shortDist, shortestDistancesForward.getWeight(v)) < 0
                        ) {
                            shortestDistancesForward.setWeight(v, shortDist)
                            openForward.add(v)
                            predecessorsForward.addPredecessor(v, vertex)

                            if (closedBackwards.contains(v)) {
                                val tmpBest = weightOperations.append(shortDist, shortestDistancesBackwards.getWeight(v)!!)

                                if (best == null || weightOperations.compare(tmpBest, best) < 0) {
                                    best = tmpBest
                                    touch = v
                                }
                            }
                        }
                    }
                }
            }

            vertex = openBackwards.removeAndGet()!!

            closedBackwards.add(vertex)

            val parentsIterable = (
                    if (graph is DirectedGraph<*, *>)
                        (graph as DirectedGraph<V, WE>).getInbound(vertex)
                    else
                        graph.getConnectedVertices(vertex)
                    )

            for (v in parentsIterable) {
                if (!closedBackwards.contains(v)) {
                    val edge = graph.getEdge(v, vertex)!!
                    if (shortestDistancesBackwards.alreadyVisited(vertex)) {
                        val shortDist = weightOperations.append(
                            shortestDistancesBackwards.getWeight(vertex)!!,
                            weightedEdges.map(edge)
                        )

                        if (!shortestDistancesBackwards.alreadyVisited(v)
                            || weightOperations.compare(shortDist, shortestDistancesBackwards.getWeight(v)) < 0
                        ) {
                            shortestDistancesBackwards.setWeight(v, shortDist)
                            openBackwards.add(v)
                            predecessorsBackwards.addPredecessor(v, vertex)

                            if (closedForward.contains(v)) {
                                val tmpBest = weightOperations.append(shortDist, shortestDistancesForward.getWeight(v)!!)

                                if (best == null || weightOperations.compare(tmpBest, best) < 0) {
                                    best = tmpBest
                                    touch = v
                                }
                            }
                        }
                    }
                }
            }
        }

        if (touch == null) {
            throw PathNotFoundException("Path from '%s' to '%s' doesn't exist in Graph '%s'", source, target, graph)
        }

        return predecessorsForward.buildPath(source, touch, target, predecessorsBackwards)
    }

    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingDijkstra(weightOperations: WO): WeightedPath<V, WE, W> {
//        var weightOperations = weightOperations
//        weightOperations = Assertions.checkNotNull(
//            weightOperations,
//            "Dijkstra algorithm can not be applied using null weight operations"
//        )

        val shortestDistances = ShortestDistances<V, W>(weightOperations)
        shortestDistances.setWeight(source, weightOperations.identity())

        val unsettledNodes = FibonacciHeap(shortestDistances)
        unsettledNodes.add(source)

        val settledNodes: MutableSet<V> = HashSet()

        val predecessors = PredecessorsList(
            graph,
            weightOperations,
            weightedEdges
        )

        // extract the node with the shortest distance
        while (!unsettledNodes.isEmpty()) {
            val vertex = unsettledNodes.removeAndGet()!!

            // destination reached, stop and build the path
            if (target == vertex) {
                return predecessors.buildPath(source, target)
            }

            settledNodes.add(vertex)

            for (v in graph.getConnectedVertices(vertex)) {
                // skip node already settled
                if (!settledNodes.contains(v)) {
                    val edge = graph.getEdge(vertex, v)!!
                    if (shortestDistances.alreadyVisited(vertex)) {
                        val shortDist = weightOperations.append(shortestDistances.getWeight(vertex)!!, weightedEdges.map(edge))

                        if (!shortestDistances.alreadyVisited(v)
                            || weightOperations.compare(shortDist, shortestDistances.getWeight(v)) < 0
                        ) {
                            // assign new shortest distance and mark unsettled
                            shortestDistances.setWeight(v, shortDist)
                            unsettledNodes.add(v)

                            // assign predecessor in shortest path
                            predecessors.addPredecessor(v, vertex)
                        }
                    }
                }
            }
        }

        throw PathNotFoundException("Path from '%s' to '%s' doesn't exist in Graph '%s'", source, target, graph)
    }
}
